{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Window Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minWindow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小窗口子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定字符串 <code>S</code> and <code>T</code>，找出 <code>S</code> 中最短的（连续）<strong>子串</strong> <code>W</code> ，使得 <code>T</code> 是 <code>W</code> 的 <strong>子序列</strong> 。</p>\n",
    "\n",
    "<p>如果 <code>S</code> 中没有窗口可以包含 <code>T</code> 中的所有字符，返回空字符串 <code>&quot;&quot;</code>。如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "S = &quot;abcdebdde&quot;, T = &quot;bde&quot;\n",
    "<strong>输出：</strong>&quot;bcde&quot;\n",
    "<strong>解释：</strong>\n",
    "&quot;bcde&quot; 是答案，因为它在相同长度的字符串 &quot;bdde&quot; 出现之前。\n",
    "&quot;deb&quot; 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>所有输入的字符串都只包含小写字母。All the strings in the input will only contain lowercase letters.</li>\n",
    "\t<li><code>S</code>&nbsp;长度的范围为&nbsp;<code>[1, 20000]</code>。</li>\n",
    "\t<li><code>T</code>&nbsp;长度的范围为&nbsp;<code>[1, 100]</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-window-subsequence](https://leetcode.cn/problems/minimum-window-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-window-subsequence](https://leetcode.cn/problems/minimum-window-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcdebdde\"\\n\"bde\"', '\"jmeqksfrsdcmsiwvaovztaqenprpvnbstl\"\\n\"u\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        size_s1, size_s2 = len(s1), len(s2)\n",
    "        length = float('inf')\n",
    "\n",
    "        # 设置s1的指针和s2的指针, 最开始都指向0(即第一个元素)\n",
    "        index_s1, index_s2 = 0, 0\n",
    "        \n",
    "        min_subsequence = \"\"\n",
    "        # 右移\n",
    "        while index_s1 < size_s1:\n",
    "            # 如果当前的字符正好是s2此时指针指向的字符\n",
    "            if s1[index_s1] == s2[index_s2]:\n",
    "                # 指针增加1, 开始匹配下一个字符\n",
    "                index_s2 += 1\n",
    "                # 这两个指针相等,代表此时的字符串已经满足了按顺序包含s2\n",
    "                if index_s2 == size_s2:\n",
    "\n",
    "                    start, end = index_s1, index_s1+1\n",
    "\n",
    "                    # 因为遍历完之后, index_s2 会超出索引范围, 减1之后指向最后一个元素\n",
    "                    index_s2 -= 1\n",
    "                    \n",
    "                    # 减少index_s2,直到所有s2中所有字符在s1中被找到\n",
    "                    # 左移? 也可以这么说\n",
    "                    ## 思路是先右移到所有s2中的字符都被包含住, 再从最右边开始往回找符合的最短字符\n",
    "                    while index_s2 >= 0:\n",
    "                        # 思路和上面右移相似, 就是这回是反方向了\n",
    "                        if s1[start] == s2[index_s2]:\n",
    "                            index_s2 -= 1\n",
    "                        start -= 1\n",
    "\n",
    "                    # 因为从最后一个索引出 减去s2的长度后, start会移动多一位 \n",
    "                    start += 1\n",
    "                    \n",
    "                    # 判断此时的是否比之前的要小\n",
    "                    if end - start < length:\n",
    "                        length = end - start\n",
    "                        min_subsequence = s1[start:end]\n",
    "\n",
    "                    # 初始化为start, 这里为什么会是start 看下图\n",
    "                    index_s1 = start\n",
    "                    index_s2 = 0\n",
    "\n",
    "            index_s1 += 1\n",
    "\n",
    "        return min_subsequence\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        i, j = 0, 0\n",
    "        min_len = float('inf')\n",
    "        left, right = 0, 0\n",
    "        while i < len(s1):\n",
    "            if s1[i] == s2[j]:\n",
    "                j += 1\n",
    "            # 完成了匹配\n",
    "            if j == len(s2):\n",
    "                right = i\n",
    "                j -= 1\n",
    "                while j >= 0:\n",
    "                    if s1[i] == s2[j]:\n",
    "                        j -= 1\n",
    "                    i -= 1\n",
    "                i += 1\n",
    "                if right - i + 1 < min_len:\n",
    "                    left = i\n",
    "                    min_len = right - left + 1\n",
    "                j = 0\n",
    "            i += 1\n",
    "        if min_len != float('inf'):\n",
    "            return s1[left: left + min_len]\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        ans= len(s1)+100\n",
    "        s_l, s, idx = -1, \"\", len(s1)\n",
    "        l = 0\n",
    "        for r in range(len(s1)):\n",
    "            if is_subsequence(s2, s1[l:r+1]):\n",
    "                while is_subsequence(s2, s1[l:r+1]):\n",
    "                    l += 1\n",
    "                if r - l + 2 < ans:\n",
    "                    ans = r - l + 2\n",
    "                    s = s1[l-1:r+1]\n",
    "                    idx = l-1\n",
    "        return s\n",
    "                \n",
    "\n",
    "def is_subsequence(needle, haystack):\n",
    "    current_pos = 0\n",
    "    for c in needle:\n",
    "        current_pos = haystack.find(c, current_pos) + 1\n",
    "        if current_pos == 0:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        \n",
    "        \n",
    "        # i指针遍历s1 j指针遍历s2 \n",
    "        # 每当s1[i]找到s2[j]时记录 j+=1 记录此时位置 直到j = len(s2)-1 说明找到了一个子序列\n",
    "        # 随后j置零 i += 1继续遍历\n",
    "        # 为了排除一些情况，如果i在遍历寻找s2[1]之前又遇到了s2[0] 则i直接从新的s2[0]开始 \n",
    "        slow, fast, j = 0, 0, 0\n",
    "        res = \"\"\n",
    "        while fast < len(s1):\n",
    "            # 记录初始位置\n",
    "            # if s1[fast] == s2[0] and j == 0:\n",
    "            #     slow = fast\n",
    "            # if j == 1 and s1[fast] == s2[0] and s1[0]:\n",
    "            #     slow = fast\n",
    "            # 遍历寻找s2[j]\n",
    "            if s1[fast] == s2[j]:\n",
    "                j += 1\n",
    "            # 找到了全部的s2\n",
    "            if j == len(s2):\n",
    "                tmp = s1[slow:fast+1]\n",
    "                s1_right = fast\n",
    "                j -= 1\n",
    "                while j >= 0:\n",
    "                    if s1[s1_right] == s2[j]:\n",
    "                        j -= 1\n",
    "                    s1_right -= 1\n",
    "                if s1_right + 1 > slow:\n",
    "                    tmp = s1[s1_right+1:fast+1]\n",
    "                    slow = s1_right + 1\n",
    "                    fast = s1_right + 1\n",
    "                if len(res) == 0 or (len(res) != 0 and len(tmp) < len(res)):\n",
    "                    res = tmp\n",
    "                j = 0\n",
    "            fast += 1\n",
    "        return res\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        i, j = 0, 0\n",
    "        min_len = float('inf')\n",
    "        left, right = 0, 0\n",
    "        while i < len(s1):\n",
    "            if s1[i] == s2[j]:\n",
    "                j += 1\n",
    "            # 完成了匹配\n",
    "            if j == len(s2):\n",
    "                right = i\n",
    "                j -= 1\n",
    "                while j >= 0:\n",
    "                    if s1[i] == s2[j]:\n",
    "                        j -= 1\n",
    "                    i -= 1\n",
    "                i += 1\n",
    "                if right - i + 1 < min_len:\n",
    "                    left = i\n",
    "                    min_len = right - left + 1\n",
    "                j = 0\n",
    "            i += 1\n",
    "        if min_len != float('inf'):\n",
    "            return s1[left: left + min_len]\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        size_s1, size_s2 = len(s1), len(s2)\n",
    "        length = float('inf')\n",
    "\n",
    "        # 设置s1的指针和s2的指针, 最开始都指向0(即第一个元素)\n",
    "        index_s1, index_s2 = 0, 0\n",
    "        \n",
    "        min_subsequence = \"\"\n",
    "        # 右移\n",
    "        while index_s1 < size_s1:\n",
    "            # 如果当前的字符正好是s2此时指针指向的字符\n",
    "            if s1[index_s1] == s2[index_s2]:\n",
    "                # 指针增加1, 开始匹配下一个字符\n",
    "                index_s2 += 1\n",
    "                # 这两个指针相等,代表此时的字符串已经满足了按顺序包含s2\n",
    "                if index_s2 == size_s2:\n",
    "\n",
    "                    start, end = index_s1, index_s1+1\n",
    "\n",
    "                    # 因为遍历完之后, index_s2 会超出索引范围, 减1之后指向最后一个元素\n",
    "                    index_s2 -= 1\n",
    "                    \n",
    "                    # 减少index_s2,直到所有s2中所有字符在s1中被找到\n",
    "                    # 左移? 也可以这么说\n",
    "                    ## 思路是先右移到所有s2中的字符都被包含住, 再从最右边开始往回找符合的最短字符\n",
    "                    while index_s2 >= 0:\n",
    "                        # 思路和上面右移相似, 就是这回是反方向了\n",
    "                        if s1[start] == s2[index_s2]:\n",
    "                            index_s2 -= 1\n",
    "                        start -= 1\n",
    "\n",
    "                    # 因为从最后一个索引出 减去s2的长度后, start会移动多一位 \n",
    "                    start += 1\n",
    "                    \n",
    "                    # 判断此时的是否比之前的要小\n",
    "                    if end - start < length:\n",
    "                        length = end - start\n",
    "                        min_subsequence = s1[start:end]\n",
    "\n",
    "                    # 初始化为start, 这里为什么会是start 看下图\n",
    "                    index_s1 = start\n",
    "                    index_s2 = 0\n",
    "\n",
    "            index_s1 += 1\n",
    "\n",
    "        return min_subsequence\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        start, end = 0, len(s1)\n",
    "        for right in range(len(s1) - 1, -1, -1):\n",
    "            if s1[right] != s2[-1]:\n",
    "                continue\n",
    "            left = right\n",
    "            t = len(s2) - 1\n",
    "            while left >= 0 and t >= 0:\n",
    "                if s1[left] == s2[t]:\n",
    "                    left -= 1\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    left -= 1\n",
    "            if t == -1 and right - left - 1 <= end - start:\n",
    "                end = right\n",
    "                start = left + 1\n",
    "        return \"\" if end - start == len(s1) else s1[start:end + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        #\n",
    "        m, n = len(s1), len(s2)\n",
    "        if m < n:\n",
    "            return \"\"\n",
    "        # i, j 为s1, s2的循环变量\n",
    "        i, j = 0, 0\n",
    "        left, right = 0, 0\n",
    "        ans = s1 + \"a\"\n",
    "        while right < m:\n",
    "            if s1[right] == s2[j]:\n",
    "                j += 1\n",
    "            right += 1\n",
    "            # s2完成匹配，找到最小窗口子序列的左边界\n",
    "            if j == n:\n",
    "                left = right-1\n",
    "                j -= 1\n",
    "                while j >= 0:\n",
    "                    if s1[left] == s2[j]:\n",
    "                        j -= 1\n",
    "                    left -= 1\n",
    "                left += 1\n",
    "                j = 0\n",
    "                # s1[left, right]即为最小子序列\n",
    "                ans = min(ans, s1[left:right], key=len)\n",
    "                right = left + 1\n",
    "            # 下一轮会重新从j==0开始匹配\n",
    "        return \"\" if len(ans) == m+1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        size_s1, size_s2 = len(s1), len(s2)\n",
    "        length = float('inf')\n",
    "\n",
    "        # 设置s1的指针和s2的指针, 最开始都指向0(即第一个元素)\n",
    "        index_s1, index_s2 = 0, 0\n",
    "        \n",
    "        min_subsequence = \"\"\n",
    "        # 右移\n",
    "        while index_s1 < size_s1:\n",
    "            # 如果当前的字符正好是s2此时指针指向的字符\n",
    "            if s1[index_s1] == s2[index_s2]:\n",
    "                # 指针增加1, 开始匹配下一个字符\n",
    "                index_s2 += 1\n",
    "                # 这两个指针相等,代表此时的字符串已经满足了按顺序包含s2\n",
    "                if index_s2 == size_s2:\n",
    "\n",
    "                    start, end = index_s1, index_s1+1\n",
    "\n",
    "                    # 因为遍历完之后, index_s2 会超出索引范围, 减1之后指向最后一个元素\n",
    "                    index_s2 -= 1\n",
    "                    \n",
    "                    # 减少index_s2,直到所有s2中所有字符在s1中被找到\n",
    "                    # 左移? 也可以这么说\n",
    "                    ## 思路是先右移到所有s2中的字符都被包含住, 再从最右边开始往回找符合的最短字符\n",
    "                    while index_s2 >= 0:\n",
    "                        # 思路和上面右移相似, 就是这回是反方向了\n",
    "                        if s1[start] == s2[index_s2]:\n",
    "                            index_s2 -= 1\n",
    "                        start -= 1\n",
    "\n",
    "                    # 因为从最后一个索引出 减去s2的长度后, start会移动多一位 \n",
    "                    start += 1\n",
    "                    \n",
    "                    # 判断此时的是否比之前的要小\n",
    "                    if end - start < length:\n",
    "                        length = end - start\n",
    "                        min_subsequence = s1[start:end]\n",
    "\n",
    "                    # 初始化为start, 这里为什么会是start 看下图\n",
    "                    index_s1 = start\n",
    "                    index_s2 = 0\n",
    "\n",
    "            index_s1 += 1\n",
    "\n",
    "        return min_subsequence\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        # 顺序匹配一遍找到右边界\n",
    "        # 拟向匹配一遍找到左边界\n",
    "        i, j  = 0, 0\n",
    "        ansLen  = len(s1)+1\n",
    "        left, right = 0, 0\n",
    "        while i < len(s1):\n",
    "            if s1[i] == s2[j]:\n",
    "                j += 1\n",
    "            if j == len(s2):\n",
    "                right = i\n",
    "                j -= 1\n",
    "                while j >= 0:\n",
    "                    if s1[i] == s2[j]:\n",
    "                        j -= 1\n",
    "                    i -= 1\n",
    "                i += 1\n",
    "                if right - i + 1 < ansLen:\n",
    "                    left = i\n",
    "                    ansLen = right - left + 1\n",
    "                j = 0\n",
    "            i += 1\n",
    "        return \"\" if ansLen == len(s1)+1 else s1[left:left+ansLen]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        \n",
    "        \n",
    "        # i指针遍历s1 j指针遍历s2 \n",
    "        # 每当s1[i]找到s2[j]时记录 j+=1 记录此时位置 直到j = len(s2)-1 说明找到了一个子序列\n",
    "        # 随后j置零 i += 1继续遍历\n",
    "        # 为了排除一些情况，如果i在遍历寻找s2[1]之前又遇到了s2[0] 则i直接从新的s2[0]开始 \n",
    "        slow, fast, j = 0, 0, 0\n",
    "        res = \"\"\n",
    "        while fast < len(s1):\n",
    "            # 记录初始位置\n",
    "            # if s1[fast] == s2[0] and j == 0:\n",
    "            #     slow = fast\n",
    "            # if j == 1 and s1[fast] == s2[0] and s1[0]:\n",
    "            #     slow = fast\n",
    "            # 遍历寻找s2[j]\n",
    "            if s1[fast] == s2[j]:\n",
    "                j += 1\n",
    "            # 找到了全部的s2\n",
    "            if j == len(s2):\n",
    "                tmp = s1[slow:fast+1]\n",
    "                s1_right = fast\n",
    "                j -= 1\n",
    "                while j >= 0:\n",
    "                    if s1[s1_right] == s2[j]:\n",
    "                        j -= 1\n",
    "                    s1_right -= 1\n",
    "                if s1_right + 1 > slow:\n",
    "                    tmp = s1[s1_right+1:fast+1]\n",
    "                slow = s1_right + 1\n",
    "                fast = s1_right + 1\n",
    "                if len(res) == 0 or (len(res) != 0 and len(tmp) < len(res)):\n",
    "                    res = tmp\n",
    "                j = 0\n",
    "            fast += 1\n",
    "        return res\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "子序列自动机\n",
    "其实这题的关键就是如何跳着去寻找窗口（关键在于T），跟自己的想法也差不多，不过稍稍难理解一点\n",
    "前缀求解的思想会更有一些dp的感觉，这个其实是挺不错的一个做法，不需要再预处理了，会更好些一点\n",
    "'''\n",
    "class Solution(object):\n",
    "    def minWindow(self, S, T):\n",
    "        cur = [i if x == T[0] else None\n",
    "               for i, x in enumerate(S)]\n",
    "        #At time j when considering T[:j+1],\n",
    "        #the smallest window [s, e] where S[e] == T[j]\n",
    "        #is represented by cur[e] = s.\n",
    "        for j in range(1, len(T)):\n",
    "            last = None\n",
    "            new = [None] * len(S)\n",
    "            #Now we would like to calculate the candidate windows\n",
    "            #\"new\" for T[:j+1].  'last' is the last window seen.\n",
    "            for i, u in enumerate(S):\n",
    "                if last is not None and u == T[j]: new[i] = last\n",
    "                if cur[i] is not None: last = cur[i]\n",
    "            cur = new\n",
    "\n",
    "        #Looking at the window data cur, choose the smallest length\n",
    "        #window [s, e].\n",
    "        ans = 0, len(S)\n",
    "        for e, s in enumerate(cur):\n",
    "            if s==None:continue\n",
    "            if s>=0 and e - s < ans[1] - ans[0]:\n",
    "                ans = s, e\n",
    "        return S[ans[0]: ans[1]+1] if ans[1] < len(S) else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "\n",
    "        table = set(s2)\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        res = ''\n",
    "        # 首先预处理每个字母出现的位置，注意需要有序保存，便于后面的二分查找\n",
    "        for i, c in enumerate(s1):\n",
    "            if c in table: # 只存有用的\n",
    "                dic1[c].append(i)     \n",
    "        # what if it only has 1 char?\n",
    "        if len(s2) == 1:\n",
    "            return s2 if s2 in dic1 else \"\"\n",
    "                \n",
    "        # 然后遍历字符s2[0]出现的位置作为起始（记为cur），\n",
    "        # 迭代地查找更新s2的下一个字符中*第一个大于cur的位置*。当遇到查找失败时直接放弃更新答案\n",
    "        for start in dic1[s2[0]]: # find the first pos of s2\n",
    "            cur = start\n",
    "            for i in range(1, len(s2)): # find 1th, 2rd..postion of s2\n",
    "                item = s2[i]\n",
    "                index = bisect.bisect_right(dic1[item], cur) # look for dic[c] after cur index\n",
    "                if i == len(s2) -1 and index < len(dic1[item]):\n",
    "                    cur_pos = dic1[item][index]\n",
    "                    if not res or cur_pos - start + 1 < len(res):\n",
    "                        res = s1[start: cur_pos + 1] \n",
    "                    break\n",
    "                if index == len(dic1[item]): # could not find\n",
    "                    break\n",
    "                cur = dic1[item][index] # index after the found val\n",
    "                \n",
    "        return res\n",
    "    \n",
    "# 时间复杂度为O(S1*s2logS1)，S1和s2分别表示对应字符串的长度\n",
    "# https://leetcode.cn/problems/minimum-window-subsequence/solutions/723540/cer-fen-cha-zhao-by-monologue-s-fmwz/?orderBy=most_votes\n",
    "\n",
    "\"\"\"\n",
    "TLE\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        n = len(s1)\n",
    "        res = \"\"\n",
    "        if len(s2) == 1:\n",
    "            return s2 if s1.find(s2) > 0 else \"\"\n",
    "        for start in range(n):\n",
    "            local_res = \"\"\n",
    "            if s1[start] == s2[0]:\n",
    "                count = 1\n",
    "                end = start + 1\n",
    "                while end < n:\n",
    "                    if s1[end] == s2[count]:\n",
    "                        count += 1\n",
    "                    if count == len(s2):\n",
    "                        local_res = s1[start: end + 1]\n",
    "                        break                \n",
    "                    end += 1\n",
    "                if res == \"\" and local_res != \"\":\n",
    "                    res = local_res\n",
    "                if local_res != \"\" and len(local_res) < len(res): # < rather than <=\n",
    "                    res = local_res\n",
    "        return res\n",
    "                    \n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Preprocessing. Time O(mn) Space O(mn)\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        m, n = len(s1), len(s2)\n",
    "        # next[i][j]: the next position of j-th alphabet at index i of s1\n",
    "        next = [None for _ in range(m)]\n",
    "        last = [-1 for _ in range(26)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            next[i] = last[:]\n",
    "            last[ord(s1[i]) - ord('a')] = i\n",
    "            \n",
    "        res = \"\"\n",
    "        for i in range(m):\n",
    "            if s1[i] != s2[0]: continue\n",
    "            lastPos = i\n",
    "            for j in range(1, n):\n",
    "                lastPos = next[lastPos][ord(s2[j]) - ord('a')]\n",
    "                if lastPos == -1: break\n",
    "            if lastPos == -1: continue\n",
    "            if not res or lastPos - i + 1 < len(res):\n",
    "                res = s1[i:lastPos+1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        m, n = len(s1), len(s2)\n",
    "        # next[i][j]: the next position of j-th alphabet at index i of s1\n",
    "        next = [None for _ in range(m)]\n",
    "        last = [-1 for _ in range(26)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            next[i] = last[:]\n",
    "            last[ord(s1[i]) - ord('a')] = i\n",
    "            \n",
    "        res = \"\"\n",
    "        for i in range(m):\n",
    "            if s1[i] != s2[0]: continue\n",
    "            lastPos = i\n",
    "            for j in range(1, n):\n",
    "                lastPos = next[lastPos][ord(s2[j]) - ord('a')]\n",
    "                if lastPos == -1: break\n",
    "            if lastPos == -1: continue\n",
    "            if not res or lastPos - i + 1 < len(res):\n",
    "                res = s1[i:lastPos+1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        m, n = len(s1), len(s2)\n",
    "        # next[i][j]: the next position of j-th alphabet at index i of s1\n",
    "        next = [None for _ in range(m)]\n",
    "        last = [-1 for _ in range(26)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            next[i] = last[:]\n",
    "            last[ord(s1[i]) - ord('a')] = i\n",
    "            \n",
    "        res = \"\"\n",
    "        for i in range(m):\n",
    "            if s1[i] != s2[0]: continue\n",
    "            lastPos = i\n",
    "            for j in range(1, n):\n",
    "                lastPos = next[lastPos][ord(s2[j]) - ord('a')]\n",
    "                if lastPos == -1: break\n",
    "            if lastPos == -1: continue\n",
    "            print(lastPos)\n",
    "            if not res or lastPos - i + 1 < len(res):\n",
    "                res = s1[i:lastPos+1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "单调队列，支持从头移除。。。\n",
    "考虑到T较短，\n",
    "记录每个字母之前，所有字母最后一次出现的位置 O(26*n)\n",
    "只有26个字母\n",
    "'''\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        temp=s1\n",
    "        s1=list(map(lambda z:ord(z)-ord('a'),s1))\n",
    "        s2=list(map(lambda z:ord(z)-ord('a'),s2))\n",
    "        n=len(s1)\n",
    "        ch=[[-1]*26 for _ in range(n)]\n",
    "        b1,e1=[],[]\n",
    "        for i,c in enumerate(s1):\n",
    "            if i!=0:\n",
    "                ch[i]=ch[i-1].copy()\n",
    "                ch[i][s1[i-1]]=i-1\n",
    "            if c==s2[0]:\n",
    "                b1.append(i)\n",
    "            if c==s2[-1]:\n",
    "                e1.append(i)\n",
    "        idb=0\n",
    "        ansl=inf\n",
    "        def calc(idb:int,ide:int)->bool:\n",
    "            n=len(s2)\n",
    "            for c in range(n-2,-1,-1):\n",
    "                ide=ch[ide][s2[c]]\n",
    "                if ide<idb:return False\n",
    "            return True\n",
    "\n",
    "        for ide in e1:\n",
    "            if idb>=len(b1):break\n",
    "            while calc(b1[idb],ide):\n",
    "                if 0<ide-b1[idb]+1<ansl:\n",
    "                    ansl=ide-b1[idb]+1  \n",
    "                    ansb=b1[idb] \n",
    "                    anse=ide\n",
    "                idb+=1\n",
    "                if idb>=len(b1):break\n",
    "        return temp[ansb:anse+1] if ansl<inf else \"\"\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, S: str, T: str) -> str:\n",
    "        # T = 'bdd'\n",
    "        # S = 'abcdebdde'\n",
    "        # dp[0] = [-1, 1, -1, -1, -1, 5, -1, -1, -1]\n",
    "        # dp[1] = [-1, -1, -1, -1, 1, -1, 5, 5, -1]\n",
    "        # dp[2] = [-1, -1, -1, -1, -1, -1, 1, 5, 1]\n",
    "\n",
    "        # Time complexity: O(MN)\n",
    "        # Space complexity: O(MN)\n",
    "\n",
    "        if len(T) > len(S): return \"\"\n",
    "        dp = [[-1] * len(S) for _ in range(len(T))]\n",
    "        for i in range(len(T)):\n",
    "            pre = -1\n",
    "            for j in range(len(S)):\n",
    "                if i == 0:\n",
    "                    if S[j] == T[i]:\n",
    "                        dp[i][j] = j\n",
    "                    continue\n",
    "                if S[j] == T[i]:\n",
    "                    dp[i][j] = pre\n",
    "                if dp[i - 1][j] != -1:\n",
    "                    pre = dp[i - 1][j]\n",
    "        res = ''\n",
    "        for j in range(len(S)):\n",
    "            if dp[-1][j] != -1:\n",
    "                sub_str = S[dp[-1][j]: j + 1]\n",
    "                if len(sub_str) < len(res) or res == '':\n",
    "                    res = sub_str\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "\n",
    "        \n",
    "        dp = [[-1 for i in range(len(s2))] for i in range(len(s1))]\n",
    "\n",
    "\n",
    "        for i in range(len(s1)):\n",
    "            for j in range(len(s2)):\n",
    "                if s1[i] == s2[j] and j == 0:\n",
    "                    dp[i][j] = i\n",
    "                elif s1[i] == s2[j] and dp[i - 1][j-1] >= 0:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] if i > 0 else -1\n",
    "        \n",
    "        length = sys.maxsize\n",
    "        res = \"\"\n",
    "\n",
    "        for i in range(len(s1)):\n",
    "            if dp[i][-1] >= 0 and i - dp[i][-1] + 1 < length:\n",
    "                length = i - dp[i][-1] + 1\n",
    "                res = s1[dp[i][-1]:i+1]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        dp = [[float('inf')] * (l2 + 1) for _ in range(l1 + 1)]\n",
    "\n",
    "        for i in range(l1 + 1):\n",
    "            dp[i][0] = 0\n",
    "        \n",
    "        for i in range(1, l1 + 1):\n",
    "            for j in range(1, min(i + 1, l2 + 1)):\n",
    "                if s1[i - 1] == s2[j - 1]:\n",
    "                    if dp[i - 1][j - 1] == float('inf'):\n",
    "                        dp[i][j] = float('inf')\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    if dp[i - 1][j] == float('inf'):\n",
    "                        dp[i][j] = float('inf')\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j] + 1\n",
    "        res = float('inf')\n",
    "        idx = -1\n",
    "        for i in range(l2, l1 + 1):\n",
    "            if dp[i][l2] != float('inf'):\n",
    "                if res > dp[i][l2]:\n",
    "                    res = dp[i][l2]\n",
    "                    idx = i\n",
    "        if idx == -1:\n",
    "            return ''\n",
    "        return s1[idx - res:idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        dp = [[0] * (l2 + 1) for _ in range(l1 + 1)]\n",
    "\n",
    "        for j in range(1, l2 + 1):\n",
    "            dp[0][j] = sys.maxsize // 2\n",
    "        \n",
    "        for i in range(1, l1 + 1):\n",
    "            for j in range(1, l2 + 1):\n",
    "                if s1[i - 1] == s2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j] + 1\n",
    "        res = sys.maxsize // 2\n",
    "        idx = -1\n",
    "        for i in range(l2, l1 + 1):\n",
    "            if dp[i][l2] < sys.maxsize // 2:\n",
    "                if res > dp[i][l2]:\n",
    "                    res = dp[i][l2]\n",
    "                    idx = i\n",
    "        if idx == -1:\n",
    "            return ''\n",
    "        return s1[idx - res:idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s1: str, s2: str) -> str:\n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        dp = [[0] * (l2 + 1) for _ in range(l1 + 1)]\n",
    "\n",
    "        for j in range(1, l2 + 1):\n",
    "            dp[0][j] = sys.maxsize // 2\n",
    "        \n",
    "        for i in range(1, l1 + 1):\n",
    "            for j in range(1, l2 + 1):\n",
    "                if s1[i - 1] == s2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j] + 1\n",
    "        min_len = sys.maxsize // 2\n",
    "        idx = -1\n",
    "        for i in range(l2, l1 + 1):\n",
    "            if dp[i][l2] < sys.maxsize // 2:\n",
    "                if min_len > dp[i][l2]:\n",
    "                    min_len = dp[i][l2]\n",
    "                    idx = i\n",
    "        if idx == -1:\n",
    "            return ''\n",
    "        return s1[idx - min_len:idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        #abcdebdde 9\n",
    "        #bde 3\n",
    "        n=len(s)\n",
    "        m=len(t)\n",
    "        @lru_cache(None)\n",
    "        def dp(i,j):\n",
    "            if j>=m: return i\n",
    "            if i>=n: return inf\n",
    "            if s[i]==t[j]: return dp(i+1,j+1)\n",
    "            else: return dp(i+1,j)\n",
    "        # 枚举匹配的起点i=0,...n-m\n",
    "        ans,res=inf,''\n",
    "        for st in range(n-m+1):\n",
    "            ed = dp(st,0) # i,j双指针匹配子序列:ed是结尾后的字符下标\n",
    "            print(st,ed)\n",
    "            if ed-st<ans:\n",
    "                ans=ed-st\n",
    "                res=s[st:ed]\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
